package com.xxwy.maxheap.practice.leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * @author xxwy
 */
public class TopkFrequent2 {

    private class Frep2 implements Comparable<Frep2> {
        public int e, freq;

        @Override
        public int compareTo(Frep2 another) {
            return Integer.compare(freq,another.freq);

        }

        public Frep2(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length ; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i])+1);
            } else {
                map.put(nums[i], 1);
            }
        }

        //java内置的PriorityQueue是最小堆
        PriorityQueue<Frep2> pq = new PriorityQueue<>();
        for (Integer key : map.keySet()) {
            if(pq.size()<k){
                pq.add(new Frep2(key,map.get(key)));
            }else if(map.get(key)>pq.peek().freq){
                pq.remove();
                pq.add(new Frep2(key,map.get(key)));
            }
        }
        LinkedList<Integer> integers = new LinkedList<>();
        while (!pq.isEmpty()){
            integers.add(pq.remove().e);
        }
        return integers;

    }

    public static void main(String[] args) {
        TopkFrequent2 topkFrequent2 = new TopkFrequent2();
        int[] arr = {1};
        List<Integer> integers = topkFrequent2.topKFrequent(arr, 1);
        System.out.println(integers);
    }
}
